package com.apkcore.bl;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * ### [260\. 只出现一次的数字 III](https://leetcode-cn.com/problems/single-number-iii/)
 * <p>
 * Difficulty: **中等**
 * <p>
 * <p>
 * 给定一个整数数组 `nums`，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 **任意顺序** 返回答案。
 * <p>
 * **进阶：**你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
 * <p>
 * **示例 1：**
 * <p>
 * ```
 * 输入：nums = [1,2,1,3,2,5]
 * 输出：[3,5]
 * 解释：[5, 3] 也是有效的答案。
 * ```
 * <p>
 * **示例 2：**
 * <p>
 * ```
 * 输入：nums = [-1,0]
 * 输出：[-1,0]
 * ```
 * <p>
 * **示例 3：**
 * <p>
 * ```
 * 输入：nums = [0,1]
 * 输出：[1,0]
 * ```
 * <p>
 * **提示：**
 * <p>
 * *   `2 <= nums.length <= 3 * 10<sup>4</sup>`
 * *   `-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1`
 * *   除两个只出现一次的整数外，`nums` 中的其他数字都出现两次
 * <p>
 * <p>
 * #### Solution
 * <p>
 * Language: ****
 * <p>
 * ```
 * 
 * ```
 */
public class _260只出现一次的数字 {

    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 3, 2, 5};
        System.out.println(Arrays.toString(new _260只出现一次的数字().singleNumber(arr)));
    }

    public int[] singleNumber1(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        int[] ans = new int[2];
        int idx = 0;
        for (int num : nums) {
            if (map.get(num) == 1) {
                ans[idx] = num;
            }
        }
        return ans;
    }

    public int[] singleNumber(int[] nums) {
        int[] ans = new int[2];
        int sum = 0;
        // 自己异或，自己异或自己=0，所以不等于0就是两个不相等的数或起来的
        for (int num : nums) {
            sum ^= num;
        }
        int k = -1;
        // 找出第k位为1的值，那么这个1肯定是这两个数异或出来的
        for (int i = 31; i >= 0 && k == -1; i--) {
            if (((sum >> i) & 1) == 1) {
                k = i;
            }
        }

        // 对 nums 进行遍历，对第 kk 位分别为 00 和 11 的元素分别求异或和（两答案必然会被分到不同的组），即为答案。
        for (int i : nums) {
            if (((i >> k) & 1) == 1) {
                ans[1] ^= i;
            } else {
                ans[0] ^= i;
            }
        }
        return ans;
    }

}
